/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2022-09-06
 * Time: 18:01
 */

//大O渐进表示法
//1.用常数1取代运行时间中的所有加法常数
//2.在修改后的运行次数函数中，只保留最高阶项。
//3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

public class Test_0906 {


    //时间复杂度为 N+ N^2/2-1/2
    //大O渐进法表示为： N^2

    //end： N     N-1     N-2 ...  N-（N-2）       N-(N-1)
    // i : N-1   N-2     N-3       1       0
    // 对 i 求和：  （1+N-1）*（N-1）/2 = N^2/2-1/2

    void bubbleSort(int[] array) {
        for (int end = array.length; end > 0; end--) {  //(0,N];
            boolean sorted = true;
            for (int i = 1; i < end; i++) {
                if (array[i - 1] > array[i]) {
                    //Swap(array, i - 1, i);
                    sorted = false;
                }
            }
            if (sorted == true) {
                break;
            }
        }
    }


    //时间复杂度为： 2^x=N
    int binarySearch(int[] array, int value) {
        int begin = 0;
        int end = array.length - 1;
        while (begin <= end) {
            int mid = begin + ((end - begin) / 2);
            if (array[mid] < value)
                begin = mid + 1;
            else if (array[mid] > value) end = mid - 1;
            else return mid;
        }
        return -1;
    }

    public static void main(String[] args) {

    }

}
